package javaInterview;

import java.util.*;

/**
 * 小红薯的好数问题
 * 
 * 题目描述：
 * 小红薯定义一个点赞数 n 为好数，当且仅当这个数的所有本质不同质因子之和为奇数。
 * 
 * 例如：
 * - 12 的本质不同质因子为 {2, 3}，和为 2+3=5（奇数），因此 12 是好数
 * - 2 的本质不同质因子为 {2}，和为 2（偶数），因此 2 不是好数
 * - 特别地，当 n=1 时无质因子，本质不同质因子之和视为 0
 * 
 * 输入格式：
 * - 第一行输入一个整数 T (1≤T≤10^4) 代表数据组数
 * - 每组测试数据：输入一个整数 n (1≤n≤10^9)，表示 Plog 的点赞数
 * 
 * 输出格式：
 * - 对于每组测试数据，如果点赞数是好数，输出 YES，否则输出 NO
 */
public class GoodNumber {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int T = scanner.nextInt();
        
        for (int i = 0; i < T; i++) {
            int n = scanner.nextInt();
            if (isGoodNumber(n)) {
                System.out.println("YES");
            } else {
                System.out.println("NO");
            }
        }
        
        scanner.close();
    }
    
    /**
     * 判断一个数是否为好数
     * 
     * 思路：
     * 1. 找出 n 的所有本质不同的质因子
     * 2. 计算这些质因子的和
     * 3. 判断和是否为奇数
     * 
     * 时间复杂度：O(sqrt(n))
     */
    public static boolean isGoodNumber(int n) {
        if (n == 1) {
            // n=1 时无质因子，和为 0（偶数），不是好数
            return false;
        }
        
        int sum = 0;  // 质因子之和
        
        // 处理质因子 2
        if (n % 2 == 0) {
            sum += 2;
            while (n % 2 == 0) {
                n /= 2;
            }
        }
        
        // 处理奇数质因子（从 3 开始，步长为 2）
        for (int i = 3; i * i <= n; i += 2) {
            if (n % i == 0) {
                sum += i;
                while (n % i == 0) {
                    n /= i;
                }
            }
        }
        
        // 如果 n > 1，说明 n 本身是一个质因子
        if (n > 1) {
            sum += n;
        }
        
        // 判断和是否为奇数
        return sum % 2 == 1;
    }
    
    /**
     * 测试用例
     */
    public static void test() {
        // 样例测试
        System.out.println("测试样例：");
        System.out.println("n=2: " + (isGoodNumber(2) ? "YES" : "NO") + " (期望: NO)");
        System.out.println("n=5: " + (isGoodNumber(5) ? "YES" : "NO") + " (期望: YES)");
        System.out.println("n=12: " + (isGoodNumber(12) ? "YES" : "NO") + " (期望: YES)");
        
        // 额外测试
        System.out.println("\n额外测试：");
        System.out.println("n=1: " + (isGoodNumber(1) ? "YES" : "NO") + " (质因子和=0，偶数)");
        System.out.println("n=3: " + (isGoodNumber(3) ? "YES" : "NO") + " (质因子和=3，奇数)");
        System.out.println("n=4: " + (isGoodNumber(4) ? "YES" : "NO") + " (质因子{2}，和=2，偶数)");
        System.out.println("n=6: " + (isGoodNumber(6) ? "YES" : "NO") + " (质因子{2,3}，和=5，奇数)");
        System.out.println("n=30: " + (isGoodNumber(30) ? "YES" : "NO") + " (质因子{2,3,5}，和=10，偶数)");
    }
}

